翻訳と辞書 Words near each other ・ Communication (Nelson Riddle album) ・ Communication (Power Station song) ・ Communication access real-time translation ・ Communication accommodation theory ・ Communication aesthetics ・ Communication and Leadership During Change ・ Communication apprehension ・ Communication art ・ Communication Arts (magazine) ・ Communication Arts Guild ・ Communication audit ・ Communication Break ・ Communication Breakdown ・ Communication Breakdown (film) ・ Communication Canada ・ Communication complexity ・ Communication design ・ Communication deviance ・ Communication diagram ・ Communication disorder ・ Communication Disorders Quarterly ・ Communication during the September 11 attacks ・ Communication Education ・ Communication endpoint ・ Communication engine ・ Communication ethics ・ Communication for Development ・ Communication for social change ・ Communication Function Classification System ・ Communication Heights Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Communication complexity ： ウィキペディア英語版 Communication complexity The notion of communication complexity was introduced by Yao in 1979, who investigated the following problem involving two separated parties (Alice and Bob). Alice receives an n-bit string x and Bob another n-bit string y, and the goal is for one of them (say Bob) to compute a certain function f(x,y) with the least amount of communication between them. Note that here we are not concerned about the number of computational steps, or the size of the computer memory used. Communication complexity tries to quantify the amount of communication required for such distributed computations. Of course they can always succeed by having Alice send her whole n-bit string to Bob, who then computes the function, but the idea here is to find clever ways of calculating f with fewer than n bits of communication. This abstract problem is relevant in many contexts: in VLSI circuit design, for example, one wants to minimize energy used by decreasing the amount of electric signals required between the different components during a distributed computation. The problem is also relevant in the study of data structures, and in the optimization of computer networks. For a survey of the field, see the book by Kushilevitz and Nisan. == Formal definition == Let $f$: X $\backslash times$ Y $\backslash rightarrow$ Z where we assume in the typical case that $X=Y=\backslash ^n$ and $Z=\backslash$. Alice draws an n-bit string $x$ $\backslash in$ X while Bob draws an n-bit string $y$ $\backslash in$ Y. By communicating to each other one bit at a time (adopting some ''communication protocol''), Alice and Bob want to compute the value of $f(x,y)$ such that at least one party knows the value at the end of the communication. At this point the answer can be communicated back so that at the cost of one extra bit, both parties will know the answer. The worst case communication complexity of this communication protocol, denoted as $D(f)$, is then defined to be :$D(f)\; =$ minimum number of bits exchanged between Alice and Bob in the worst case Using the above definition, it is useful to think of the function $f$ as a matrix $A$ (called the ''input matrix'') where each row of the matrix corresponds to $x$ $\backslash in$ X and each column corresponds to $y$ $\backslash in$ Y. An entry in the input matrix is $A\_$. Then, as and when each party communicates a bit to the other, the number of choices for the answer reduces as this eliminates a set of rows/columns resulting in a submatrix of A. More formally, a set R $\backslash subseteq$ X $\backslash times$ Y is called a ''(combinatorial) rectangle'' if whenever $(x\_1,y\_1)$ $\backslash in$ R and $(x\_2,y\_2)$ $\backslash in$ R then $(x\_1,y\_2)$ $\backslash in$ R. Equivalently, R can also be viewed as a submatrix of the input matrix A such that R = M $\backslash times$ N where M $\backslash subseteq$ X and N $\backslash subseteq$ Y. Consider the case when $k$ bits are already exchanged between the parties. Now, for a particular $h$ $\backslash in$ $\backslash ^k$, let us define a matrix :$T\_$ Then, $T\_\}$ is a rectangle and a submatrix of A. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Communication complexity」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.